package com.zk.algorithm.tree;

import com.zk.algorithm.bean.BinaryTreeNode;
import com.zk.algorithm.factory.TreeFactory;

import java.util.Stack;

/**
 * 迭代版本的后序遍历
 *
 * stack2: 存储后序遍历的反序元素
 * stack1: 生成后序遍历的反序元素: 变种前序遍历 root left right => root right left
 */
public class IterativePostorder {

    public void postOrderIterative(BinaryTreeNode root) {
        // Create two stacks

        // s1 变种前序遍历 root left right => root right left
        Stack<BinaryTreeNode> s1 = new Stack<>();
        // s2 存储后序遍历的元素
        Stack<BinaryTreeNode> s2 = new Stack<>();

        if (root == null)
            return;

        // push root to first stack
        s1.push(root);

        // Run while first stack is not empty
        while (!s1.isEmpty()) {
            // Pop an item from s1 and push it to s2
            BinaryTreeNode temp = s1.pop();
            s2.push(temp);

            // Push left and right children of
            // removed item to s1
            if (temp.getLeft() != null)
                s1.push(temp.getLeft());
            if (temp.getRight() != null)
                s1.push(temp.getRight());
        }

        // Print all elements of second stack
        while (!s2.isEmpty()) {
            BinaryTreeNode temp = s2.pop();
            System.out.print(temp.getVal() + ",");
        }
    }

    public static void main(String...args) {
        new IterativePostorder().postOrderIterative(TreeFactory.buildCompleteTree(7));
    }

}
